//
//  Heap.c
//  对堆排序的二次实现
//
//  Created by Yan Zihao on 2024/11/25.
//
#include "Heap.h"

void HeapInit(Heap* php)
{
    assert(php);
    php->_a = NULL;
    php->_capacity = php->_size = 0;
}

void HeapDestory(Heap* php)
{
    assert(php);
    free(php->_a);
    php->_a = NULL;
    php->_capacity = php->_size = 0;
}

void Swap(HPDataType* a, HPDataType* b)
{
    HPDataType tmp = *a;
    *a = *b;
    *b = tmp;
}

void AdjustUp(HPDataType* a, int child)
{
    int parent = (child - 1) / 2;
    while(child > 0)
    {
        if(a[parent] > a[child])
        {
            Swap(&a[parent], &a[child]);
            parent = child;
            child = (parent - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

void HeapPush(Heap* php, HPDataType x)
{
    assert(php);
    if(php->_capacity == php->_size)
    {
        int newcapacity = php->_capacity == 0 ? 4 : 2 * (php->_capacity);
        HPDataType* tmp = (HPDataType*)realloc(php->_a, newcapacity*sizeof(HPDataType));
        if(tmp == NULL)
        {
            perror("realloc fail");
            return;
        }
        php->_a = tmp;
        php->_capacity = newcapacity;
    }
    php->_a[php->_size++] = x;
    
    AdjustUp(php->_a, php->_size - 1);
}

void AdjustDown(HPDataType* a, int parent,int n)
{
    int child = parent * 2 + 1;
    while(child < n)
    {
        if(a[child] > a[child + 1] && child + 1 < n)
        {
            child++;
        }
        if(a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }

}

void HeapPop(Heap* php)
{
    assert(php);
    assert(php->_size > 0);
    Swap(&php->_a[0], &php->_a[php->_size - 1]);
    php->_size--;
    AdjustDown(php->_a, 0, php->_size);
}

HPDataType HeapTop(Heap* php)
{
    assert(php);
    assert(php->_size > 0);
    return php->_a[0];
}

bool HPEmpty(Heap* php)
{
    assert(php);

    return php->_size == 0;
}

int main(void)
{
    int arr[] = {3,6,2,7,4};
    Heap HP;
    HeapInit(&HP);
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < n; i++)
    {
        HeapPush(&HP, arr[i]);
    }
    HeapPop(&HP);
    HeapPop(&HP);
    HeapPop(&HP);
    for (int i = 0; i < HP._size; i++)
    {
        printf("%d ",HP._a[i]);
    }
    
    return 0;
}
